A number of types of multiprocessor computer systems have been developed which integrate a number of processors to increase the system's processing power beyond that which can be provided by a single processor. In a multiprocessor computer system, a plurality of processing nodes are interconnected by communication links which may comprise any suitable mechanism for transferring digital information, including, for example, wires, optical fibers, and the like.
A variety of types of interconnection arrangements have been developed for interconnecting processors in a multiprocessor computer system designed according to the distributed memory model, organized in a number of topologies. For small systems, comprising two or three processing nodes, a simple bus to which all processing nodes are connected may suffice. However, as the number of processing nodes increases, contention for the bus increases, which can slow down information transfer and the processing capability of the respective systems.
A variety of types of interconnection arrangements have been developed for interconnecting processors in a multiprocessor computer system, organized in a number of topologies. For small systems, comprising two or three processing nodes, a simple bus to which all processing nodes are connected may suffice. However, as the number of processing nodes increases, contention for the bus increases, which can slow down information transfer and the processing capability of the respective systems.
Most interconnection topologies that have been proposed, studied and/or implemented, other than the aforementioned bus, have been developed for systems including a large number of processing nodes, in particular, systems numbering in the hundreds or thousands of processing nodes. However, many systems that are desired commercially are much smaller, having, for example, as few as four or five processing nodes, up to as many as fifteen to twenty. For such systems, interconnection topologies that have been developed for large systems are often not economical. Another problem with such interconnection topologies is that they are typically based on the assumption that the systems with which they are to be used include a number of processing nodes corresponding to a power of two, and will be most economical for those numbers of processing nodes. If, for example, such a system at one time has a number of processing nodes corresponding to a power of two, it may be necessary to increase the interconnection subsystem considerably even if it is desired to increase the number of processing nodes by only one.
A number of communications metrics have been developed for assessing the various interconnection topologies, including the respective topology's "diameter," its "average distance," and its "normalized bisection bandwidth." A topology's diameter corresponds to the maximum distance, measured in number of communication links, over all pairs of processing nodes in the multiprocessor computer system, of the minimum number of communication links between respective processing node pairs. Essentially, if one "source" processing node is to transfer information to another "destination" processing node that is not connected directly thereto, the information will be transferred over a path from the source processing node, through one or more intermediate processing nodes until it is delivered to the destination processing node. The diameter generally indicates the maximum number of communication links required to transfer information from any processing node to any other processing node in the multiprocessor computer system, which, in turn, is a measure of the delay in transferring the information.
The average distance, on the other hand, is the average, over all pairs of processing nodes in the multiprocessor computer system, of the minimum distance, also measured in number of communication links, between respective processing node pairs, and is a general indication of the average delay, also represented in numbers of communication links, required to transfer information from one processing node to another in the multiprocessor computer system.
Finally, the normalized bisection bandwidth is determined by dividing the multiprocessor computer system into two sections, or "partitions," and determining the number of communication links between the processing nodes in the two partitions; the normalized bisection bandwidth is the smallest number of communication links for any set of such partitions that may be formed in the multiprocessor computer system, divided by one-half the number of processing nodes in the system. If the multiprocessor computer system contains an even number of processing nodes, each partition will have the same number of processing nodes. On the other hand, if the multiprocessor computer system contains an odd number of processing nodes, one partition will have one more processing node than the other partition. In any case, the normalized bisection bandwidth is a measure of the information-transfer bandwidth, represented in numbers of communication links, between partitions of processing nodes in the multiprocessor computer system.